The present invention relates generally to optimization of computer programs written in Hardware Description Languages (HDLs), and more specifically to a method of transforming variable loops into constant loops.
In modern circuit design, particularly in the development of ASICs (Application Specific Integrated Circuits) and FPGAs (Field Programmable Gate Arrays), extensive use is made of models written using HDLs. Examples of tools for processing HDLs in use today include DesignCompiler™ of Synopsis, Inc., and DesignVerifier™ of Chrysalis. Examples of HDLs in use today include Verilog and VHDL (Very high speed integrated circuits HDL). In a typical design process, a hardware designer writes an HDL program representing the high level operation and/or design of a circuit. This HDL program may then be compiled and executed in order to test and verify the circuit design. Compilation of an HDL program is also sometimes referred to as “synthesizing” the HDL into a lower level representation of the circuit. The compiler for an HDL program is a type of computer aided design (CAD) system.
The compiled output of a CAD tool used to process an HDL program might describe a physical layout of gates which implement the circuit described by the HDL input. For example, in some systems, HDL is processed by what is referred to as a “gate synthesizer” program, the output of which is a “netlist” describing a network of gates within a physical circuit. The netlist output by a gate synthesizer may itself be used to test potential circuit designs, or even as the basis for automatic fabrication of actual circuits.
Circuit models written in HDL often involve looping statements. Illustrative types of looping statements are shown in FIG. 1 and FIG. 2. A “FOR” loop 10 looping statement is depicted in FIG. 1, and a “WHILE” loop 12 looping statement is shown in FIG. 2. The looping statements shown in FIG. 1 and FIG. 2 are specific examples of the many types of looping statements which may be employed to represent the structure of a circuit using an HDL.
In general, looping statements contain an initial expression, an exit expression, and an increment/decrement expression, as well as a loop body consisting of one or more of statements. For purposes of illustration, a generalized FOR loop statement 14 is shown in FIG. 3. The FOR loop statement 14 of FIG. 3 is shown including initial expression INIT 16, exit expression EXIT 18, increment/decrement expression INC 20, and a loop body BODY—OF—STATEMENTS 22.
Looping statements may be categorized into what are referred to as constant looping statements and variable looping statements. A looping statement is a constant looping statement if both the initial expression and the exit expression involve only constants and the loop index. If the initial expression and exit expression of a looping statement do not both involve only constants and the loop index, then that looping statement is considered a variable looping statement. The looping statement 10 of FIG. 1 is an example of a constant looping statement, and the looping statement 12 of FIG. 2 is an example of a variable looping statement.
Hardware models developed using HDLs are often compiled prior to execution. Many HDL compilers perform a type of compile time optimization known as “loop unrolling”. Loop unrolling is a process in which loop overhead can be reduced by expressly replicating the body of the loop within the program, thus reducing the iterations through the loop. In some cases, a looping statement may be completely eliminated by replicating the loop body a number of times dictated by the initial, exit, and increment/decrement expressions of the loop statement. Loop unrolling simplifies compilation and makes it possible for many programs to be executed more efficiently. In particular, loop unrolling is known to enable greater degrees of program parallelization, thus potentially improving program execution speed.
Now considering FIG. 1, which is shown including a loop body 11, a loop unrolling optimization would transform the original looping statement 10 into the equivalent statements 24 of FIG. 4, completely eliminating the loop. As shown in FIG. 4, the loop index i from the original looping statement 10 of FIG. 1 is replaced by constants as the loop is unrolled. Based on the construction of the looping statement 10, the statements within the loop body 11 need to be performed twice.
A significant problem in existing computer aided design (CAD) systems for hardware circuit design, is that they fail to provide loop unrolling for variable looping statements. In particular, the above mentioned tools for processing HDLs—DesignCompiler™ of Synopsis, Inc., and DesignVerifier™ of Chrysalis, are unable to perform straight-forward loop unrolling for variable looping statements. Accordingly, such existing systems cannot perform the transformation from the looping statement 10 of FIG. 1 to the statements 24 in FIG. 4 for variable looping statements, such as the looping statement 12 of FIG. 2. This problem arises from the fact that the exact number of times the loop body of a variable looping statement must be replicated cannot be determined at compilation time. Thus, variable looping statements are often not synthesizable into netlists or other circuit models developed from HDLs.
For these reasons, it would be desirable to have a system for processing HDL programs which is capable of unrolling variable looping statements.